package com.acwing.partition4;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/4/2 10:21
 */
public class AC364网络 {

    private static final int N = 100010, M = 800010, D = 17;
    private static int[] h = new int[N], hc = new int[N], e = new int[M], ne = new int[M];
    private static int[] dfn = new int[N], low = new int[N], edcc = new int[N];
    private static boolean[] bridge = new boolean[M];
    private static int[][] f = new int[N][D + 1];
    private static int[] q = new int[N], depth = new int[N];
    private static int n, m, tot = 0, timestamp = 0, edccId = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        //大体上可分为两步，首先tarjan找出所有的边双连通分量进行缩点；然后在缩点图上跑lca
        for (int k = 1; ; k++) {
            String[] ss = reader.readLine().split(" ");
            n = Integer.parseInt(ss[0]);
            m = Integer.parseInt(ss[1]);
            if (n == 0 && m == 0) break;
            reset();
            //tarjan预处理，负责找出双连通分量和缩点
            tarjan();
            lca(k);
        }
        writer.flush();
    }

    private static void tarjan() throws IOException {
        for (int i = 0; i < m; i++) {
            String[] ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]);
            add(h, a, b);
            add(h, b, a);
        }
        //本题属于无向连通图，只需要做一次tarjan就可以访问所有节点
        tarjan(1, -1);
        //edcc标号并缩点
        for (int i = 1; i <= n; i++) {
            if (edcc[i] == 0) {
                edccId++;
                dfs(i);
            }
        }
        //重置bridge，后续只会使用到缩点图的桥
        for (int i = 0; i < M; i++) bridge[i] = false;
        //本题缩点之后一定是树，所有新边都是桥，初始桥的数量就是节点数-1
        int t = tot;
        for (int i = 0; i < t; i++) {
            int u = e[i ^ 1], v = e[i];
            if (edcc[u] == edcc[v]) continue;
            add(hc, edcc[u], edcc[v]);
            //所有的树边都是割边
            bridge[tot - 1] = true;
        }
    }

    private static void lca(int k) throws IOException {
        bfs(1);
        int bridgeCnt = edccId - 1, q = Integer.parseInt(reader.readLine());
        writer.write(String.format("Case %d:\n", k));
        while (q-- > 0) {
            //如果新加的边是在同一个edcc，割边不变；如果新加的边属于不同的edcc，初始化lca，并从当前两个节点分别向lca走，经过的边数就是原来的桥，
            //但是加入了新边后就会成环，经过的边不再是桥，此时需要用 bridgeCnt-两节点经过的边数和
            String[] ss = reader.readLine().split(" ");
            int a = edcc[Integer.parseInt(ss[0])], b = edcc[Integer.parseInt(ss[1])];
            if (a == b) {
                writer.write(bridgeCnt + "\n");
                continue;
            }
            //分别以a和b朝着lca节点移动，记录中途中的桥的数量
            int c = lca(a, b);
            bridgeCnt -= dfs(a, c) + dfs(b, c);
            writer.write(bridgeCnt + "\n");
        }
        writer.write("\n");
    }

    private static int dfs(int u, int lca) {
        if (u == lca) return 0;
        int res = 0;
        for (int i = hc[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (v == f[u][0]) {
                //如果当前边是桥，记录+1，由于连接了a->b，当前边不再是桥
                if (bridge[i]) {
                    res++;
                    bridge[i] = bridge[i ^ 1] = false;
                }
                res += dfs(v, lca);
            }
        }
        return res;
    }

    private static int lca(int x, int y) {
        if (depth[x] < depth[y]) {
            int t = x;
            x = y;
            y = t;
        }
        for (int i = D; i >= 0; i--) {
            if (f[x][i] != 0 && depth[f[x][i]] >= depth[y]) {
                x = f[x][i];
            }
        }
        if (x == y) return x;
        for (int i = D; i >= 0; i--) {
            if (f[x][i] != f[y][i]) {
                x = f[x][i];
                y = f[y][i];
            }
        }
        return f[x][0];
    }

    private static void bfs(int root) {
        int hh = 0, tt = 0;
        depth[root] = 1;
        q[0] = root;
        while (hh <= tt) {
            int u = q[hh++];
            for (int i = hc[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (depth[v] != 0) continue;
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                for (int j = 1; j <= D; j++) {
                    int anc = f[v][j - 1];
                    f[v][j] = f[anc][j - 1];
                }
                q[++tt] = v;
            }
        }
    }

    private static void dfs(int u) {
        edcc[u] = edccId;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (edcc[v] != 0 || bridge[i]) continue;
            dfs(v);
        }
    }

    private static void tarjan(int u, int inBridge) {
        dfn[u] = low[u] = ++timestamp;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dfn[v] == 0) {
                tarjan(v, i);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = true;
            } else if ((inBridge ^ 1) != i) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
    }

    private static void add(int[] h, int a, int b) {
        e[tot] = b;
        ne[tot] = h[a];
        h[a] = tot++;
    }

    private static void reset() {
        tot = edccId = timestamp = 0;
        for (int i = 0; i < N; i++) {
            h[i] = hc[i] = -1;
            dfn[i] = low[i] = depth[i] = edcc[i] = 0;
        }
        for (int i = 0; i < M; i++) {
            e[i] = ne[i] = 0;
            bridge[i] = false;
        }
    }
}
